package com.datastructure.test.findkthnum;

import java.util.Arrays;

public class FindKthNum {

    public static void main(String[] args) {
        FindKthNum findKthNum = new FindKthNum();
        int[] arr1 = {1,2,3,4};
        int[] arr2 = {1,3,4};
        int kthNum = findKthNum.findKthNum(arr1, arr2, 2);
        System.out.println(kthNum);
    }

    public int findKthNum (int[] arr1, int[] arr2, int target) {
        // write code here
        int[] tempArray = new int[arr1.length+arr2.length];
        System.arraycopy(arr1,0,tempArray,0,arr1.length);
        System.arraycopy(arr2,0,tempArray,arr1.length,arr2.length);
        Arrays.sort(tempArray);
        return tempArray[target-1];
    }

    public int findKthNum1 (int[] arr1, int[] arr2, int target) {
        // write code here
        final int len1 = arr1.length;
        final int len2 = arr2.length;
        int i = 0;
        int j = 0;

        while (i < len1 && j < len2 && i + j < target) {
            if (arr1[i] <= arr2[j]) {
                i++;
            } else {
                j++;
            }
        }

        if (i < len1 && j < len2) {
            return arr1[i-1];
        }

        if (i < len1) {
            return arr1[target - j - 1];
        } else {
            return arr2[target - i - 1];
        }
        // Math.min
    }

}
